package leetcode.递归回溯BFSDFS;

/**
 * 计算 pow
 *
 * 二分法
 * 注意数据溢出问题
 */
public class Test50Pow {

    // 这种办法虽然可以，但是超时
    public static double myPow2(double x, int n) {
        // 2^4=2*2*2*2
        if (n == 0)
            return 1;
        double res = x;
        for (int i = 1; i < Math.abs(n); i++) {
            res *= x;
        }
        return n < 0 ? 1 / res : res;
    }

    // 既然遍历会导致超时，那么就二分
    public static double myPow(double x, int n) {
        boolean f = false;
        if (n < 0) {
            f = true;
            n = -n;
        }
        double ans = div(x, n);
        return f ? 1 / ans : ans;
    }

    public static double div(double x, int n) {
        if (n == 1)
            return x;
        if (n == 0)
            return 1;
        double temp = div(x, n / 2);
        double res = 0.0;
        if (n % 2 != 0) {
            res = x * temp * temp;
        } else {
            res = temp * temp;
        }
        return res;
    }


    public static void main(String[] args) {
//        System.out.println(myPow(2, 4));
        System.out.println(myPow(2.0, -2147483648));
//        System.out.println(myPow(2.10000, 3));
//        System.out.println(myPow(2.00000, -2));
    }
}
